package com.mzy.linear_struct.subject;

import java.util.Arrays;

/**
 * @Author: codermzy
 * @Date: 2024/04/15/16:47
 * @Description:
 */
public class 在排序数组中查找元素的第一个和最后一个位置34 {

    public int[] searchRange(int[] nums, int target) {
        int[] answer = {-1, -1};
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (answer[0] == -1) {
                    answer[0] = i;
                } else {
                    answer[1] = i;
                }
            }
        }
        if (answer[1] == -1) {
            answer[1] = answer[0];
        }
        return answer;
    }

    public int[] searchRange1(int[] nums, int target) {

        if (nums == null) {
            return new int[]{-1, -1};
        }

        if (nums.length < 1) {
            return new int[]{-1, -1};
        }

        int[] answer = {-1, -1};
        int l = 0;
        int r = nums.length - 1;

        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] >= target) {
                r = mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            }
        }
        // 判断是否找到的下标上的值是否是 target
        if (nums[l] != target) {
            return new int[]{-1, -1}; // 没有找到 target 即当前数组中没有元素
        }
        // 此时 l 和 r 都指向第一次出现的 target 位置
        answer[0] = l;
        answer[1] = l;
        // 修改 r 的指针到末尾
        r = nums.length - 1;
        l = 0;
        while (l < r) {
            int mid = l + ((r - l + 1) >> 1);

            if (nums[mid] <= target) {
                l = mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            }
        }
        answer[1] = r;
        return answer;
    }


    public int[] searchRange2(int[] nums, int target) {
        int upper = upperBound(nums, target);
        int low = lowerBound(nums, target);
        // 不存在情况
        if (upper < low) {
            return new int[]{-1, -1};
        }
        return new int[]{low, upper};
    }

    // 计算下边界
    int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            // 这里需要注意，计算mid
            int mid = left + ((right - left) >> 1);
            if (target <= nums[mid]) {
                // 当目标值小于等于nums[mid]时，继续在左区间检索，找到第一个数
                right = mid - 1;

            } else if (target > nums[mid]) {
                // 目标值大于nums[mid]时，则在右区间继续检索，找到第一个等于目标值的数
                left = mid + 1;

            }
        }
        return left;
    }

    // 计算上边界
    int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target >= nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        // int[] nums = {1, 3, 4, 5, 5, 5, 5, 5, 9};
        int[] nums = {5, 7, 7, 8, 8, 10};
        //            0  1  2  3  4  5  6  7  8
        int[] range = new 在排序数组中查找元素的第一个和最后一个位置34().searchRange1(nums, 6);


        System.out.println(Arrays.toString(range));
    }
}
